{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Width of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: widthOfBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树最大宽度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，返回树的 <strong>最大宽度</strong> 。</p>\n",
    "\n",
    "<p>树的 <strong>最大宽度</strong> 是所有层中最大的 <strong>宽度</strong> 。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>每一层的 <strong>宽度</strong> 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 <code>null</code> 节点，这些 <code>null</code> 节点也计入长度。</p>\n",
    "\n",
    "<p>题目数据保证答案将会在&nbsp; <strong>32 位</strong> 带符号整数范围内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg\" style=\"width: 359px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,3,2,5,3,null,9]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg\" style=\"width: 442px; height: 422px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,3,2,5,null,null,9,6,null,7]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg\" style=\"width: 289px; height: 299px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,3,2,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目范围是 <code>[1, 3000]</code></li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-width-of-binary-tree](https://leetcode.cn/problems/maximum-width-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-width-of-binary-tree](https://leetcode.cn/problems/maximum-width-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,5,3,null,9]', '[1,3,2,5,null,null,9,6,null,7]', '[1,3,2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        arr = [[root, 1]]\n",
    "        while arr:\n",
    "            tmp = []\n",
    "            for node, index in arr:\n",
    "                if node.left:\n",
    "                    tmp.append([node.left, index * 2])\n",
    "                if node.right:\n",
    "                    tmp.append([node.right, index * 2 + 1])\n",
    "            res = max(res, arr[-1][1] - arr[0][1] + 1)\n",
    "            arr = tmp\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: BFS + Indexing\n",
    "    time: O(n), space: O(n)\n",
    "    \"\"\"\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "\n",
    "        queue = [(root, 1)]\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            level = []\n",
    "\n",
    "            for _ in range(length):\n",
    "                node, idx = queue.pop(0)\n",
    "                level.append(idx)\n",
    "                if node.left:\n",
    "                    queue.append((node.left, 2*idx))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, 2*idx+1))\n",
    "            res = max(res, max(level)-min(level)+1)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        stack = [[root,1]]\n",
    "        while stack:\n",
    "            begin_v = stack[0][1]\n",
    "            for i in range(len(stack)):\n",
    "                cur,v = stack.pop(0)\n",
    "                if cur.left:\n",
    "                    stack.append([cur.left,2*v])\n",
    "                if cur.right:\n",
    "                    stack.append([cur.right,2*v+1])\n",
    "                res = max(v-begin_v+1,res)\n",
    "        return res\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        q = deque([(root, 1)])\n",
    "        while q:\n",
    "            (node, index) = q[0]\n",
    "            min_index, max_index = index, index\n",
    "            for _ in range(len(q)):\n",
    "                (node, index) = q.popleft()\n",
    "                if index > max_index:\n",
    "                    max_index = index\n",
    "                if node.left:\n",
    "                    q.append((node.left, index*2))\n",
    "                if node.right:\n",
    "                    q.append((node.right, index*2+1))\n",
    "            self.res = max(self.res, max_index-min_index+1)\n",
    "        return self.res\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        給一個 binary tree 的 root\n",
    "        回傳在所有 level 中的最大寬度\n",
    "        width: \n",
    "        1. 在某一列(level)的最左邊 node(不是null) ~ 最右邊 node(不是null)\n",
    "        2. 在這兩個端點中如果有 null, 那也把它加入計算\n",
    "        \"\"\"\n",
    "        \n",
    "        # 在 node = null 的狀況下, 做一個\"假的 node\"(會超時)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        max_width = 0\n",
    "        \n",
    "        while q:\n",
    "            result = []\n",
    "            #print(f\"{q=}\")\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "                else:\n",
    "                    node = TreeNode(val=101)\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            left  = 0\n",
    "            right = len(result) - 1\n",
    "            while left <= right:\n",
    "                if result[left] == 101:\n",
    "                    left  += 1\n",
    "                elif result[right] == 101:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    max_width = max(max_width, right - left + 1)\n",
    "                    break\n",
    "            \n",
    "            count = 0\n",
    "            for i in range(len(q)):\n",
    "                if not q[i]:\n",
    "                    count += 1\n",
    "            if count == len(q):\n",
    "                break\n",
    "        return max_width\n",
    "        \"\"\"\n",
    "        \n",
    "        # 給每個 node 都打上 count (太難了想不到...)\n",
    "        \"\"\"\n",
    "             1 (假設 root 是 count 1)\n",
    "            / \\\n",
    "           2   3\n",
    "           root.left  的記號是 (count * 2)\n",
    "           root.right 的記號是 (count * 2) + 1\n",
    "        \n",
    "        在每一層結束的時候, 計算 result[-1] - result[0] + 1\n",
    "        這就是那一層的最大寬度\n",
    "        \"\"\"\n",
    "        \n",
    "        # 要額外用一個 result, 它紀錄存在的 node 的 count\n",
    "        \"\"\"\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        \n",
    "        max_width = 0\n",
    "        while q:\n",
    "            result = []\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node:\n",
    "                    result.append(count)\n",
    "                    q.append([node.left,  (count * 2)])\n",
    "                    q.append([node.right, (count * 2) + 1])\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            if result:\n",
    "                max_width = max(max_width, result[-1] - result[0] + 1)\n",
    "        return max_width\n",
    "        \"\"\"\n",
    "        \n",
    "        # 不用 result 的方法: 有 left, right 的時候才紀錄 count\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        max_width = 1 # edge case: [1]\n",
    "        \n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node.left:  q.append([node.left,  (count * 2)])\n",
    "                if node.right: q.append([node.right, (count * 2) + 1])\n",
    "            if q:\n",
    "                max_width = max(max_width, q[-1][1] - q[0][1] + 1)\n",
    "        return max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        給一個 binary tree 的 root\n",
    "        回傳在所有 level 中的最大寬度\n",
    "        width: \n",
    "        1. 在某一列(level)的最左邊 node(不是null) ~ 最右邊 node(不是null)\n",
    "        2. 在這兩個端點中如果有 null, 那也把它加入計算\n",
    "        \"\"\"\n",
    "        \n",
    "        # 在 node = null 的狀況下, 做一個\"假的 node\"(會超時)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        max_width = 0\n",
    "        \n",
    "        while q:\n",
    "            result = []\n",
    "            #print(f\"{q=}\")\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "                else:\n",
    "                    node = TreeNode(val=101)\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            left  = 0\n",
    "            right = len(result) - 1\n",
    "            while left <= right:\n",
    "                if result[left] == 101:\n",
    "                    left  += 1\n",
    "                elif result[right] == 101:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    max_width = max(max_width, right - left + 1)\n",
    "                    break\n",
    "            \n",
    "            count = 0\n",
    "            for i in range(len(q)):\n",
    "                if not q[i]:\n",
    "                    count += 1\n",
    "            if count == len(q):\n",
    "                break\n",
    "        return max_width\n",
    "        \"\"\"\n",
    "        \n",
    "        # 給每個 node 都打上 count (太難了想不到...)\n",
    "        \"\"\"\n",
    "             1 (假設 root 是 count 1)\n",
    "            / \\\n",
    "           2   3\n",
    "           root.left  的記號是 (count * 2)\n",
    "           root.right 的記號是 (count * 2) + 1\n",
    "        \n",
    "        在每一層結束的時候, 計算 result[-1] - result[0] + 1\n",
    "        這就是那一層的最大寬度\n",
    "        \"\"\"\n",
    "        \n",
    "        # 要額外用一個 result, 它紀錄存在的 node 的 count\n",
    "        \"\"\"\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        \n",
    "        max_width = 0\n",
    "        while q:\n",
    "            result = []\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node:\n",
    "                    result.append(count)\n",
    "                    q.append([node.left,  (count * 2)])\n",
    "                    q.append([node.right, (count * 2) + 1])\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            if result:\n",
    "                max_width = max(max_width, result[-1] - result[0] + 1)\n",
    "        return max_width\n",
    "        \"\"\"\n",
    "        \n",
    "        # 不用 result 的方法: 有 left, right 的時候才紀錄 count\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        max_width = 1 # edge case: [1]\n",
    "        \n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node.left:  q.append([node.left,  (count * 2)])\n",
    "                if node.right: q.append([node.right, (count * 2) + 1])\n",
    "                    \n",
    "            # 在這層時, q 裡面放的都是這一層的數字\n",
    "            if q:\n",
    "                max_width = max(max_width, q[-1][1] - q[0][1] + 1)\n",
    "        return max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "\n",
    "        q = deque()\n",
    "        q.append([root,1])\n",
    "\n",
    "        while q:\n",
    "            minInd = float('inf')\n",
    "            maxInd = float('-inf')\n",
    "            for x in range(len(q)):\n",
    "                node, ind = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append([node.left, ind * 2])\n",
    "                    minInd = min(minInd, ind * 2)\n",
    "                    maxInd = max(maxInd, ind * 2)\n",
    "                if node.right:\n",
    "                    q.append([node.right, ind * 2 + 1])\n",
    "                    minInd = min(minInd, ind * 2 + 1)\n",
    "                    maxInd = max(maxInd, ind * 2 + 1)\n",
    "\n",
    "            res = max(maxInd - minInd + 1, res)\n",
    "\n",
    "        return res\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        # if not root or (not root.left and not root.right):\n",
    "            # return 0\n",
    "\n",
    "        q = deque()\n",
    "        q.append([root,1])\n",
    "\n",
    "        while q:\n",
    "            minInd = float('inf')\n",
    "            maxInd = float('-inf')\n",
    "            for x in range(len(q)):\n",
    "                node, ind = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append([node.left, ind * 2])\n",
    "                    minInd = min(minInd, ind * 2)\n",
    "                    maxInd = max(maxInd, ind * 2)\n",
    "                if node.right:\n",
    "                    q.append([node.right, ind * 2 + 1])\n",
    "                    minInd = min(minInd, ind * 2 + 1)\n",
    "                    maxInd = max(maxInd, ind * 2 + 1)\n",
    "\n",
    "            res = max(maxInd - minInd + 1, res)\n",
    "\n",
    "        return res\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, queue = 0, deque([(1, root)])\n",
    "        while queue:\n",
    "            mn, mx = inf, 0\n",
    "            for _ in range(len(queue)):\n",
    "                code, node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append((code * 2, node.left))\n",
    "                if node.right:\n",
    "                    queue.append((code * 2 + 1, node.right))\n",
    "                mn, mx = min(code, mn), max(code, mx)\n",
    "            ans = max(ans, mx - mn + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 层序遍历\n",
    "        ans = 0\n",
    "        if not root:\n",
    "            return ans\n",
    "        queue = [(root, 0)]\n",
    "\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            cur = queue[-1][1] - queue[0][1] + 1\n",
    "            ans = max(ans, cur)\n",
    "            for _ in range(n):\n",
    "                node, idx = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append((node.left, 2 * idx + 1))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, 2 * idx + 2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        max_width = 0\n",
    "        # queue of elements [(node, col_index)]\n",
    "        queue = deque()\n",
    "        queue.append((root, 0))\n",
    "\n",
    "        while queue:\n",
    "            level_length = len(queue)\n",
    "            _, level_head_index = queue[0]\n",
    "            # iterate through the current level\n",
    "            for _ in range(level_length):\n",
    "                node, col_index = queue.popleft()\n",
    "                # preparing for the next level\n",
    "                if node.left:\n",
    "                    queue.append((node.left, 2 * col_index))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, 2 * col_index + 1))\n",
    "\n",
    "            # calculate the length of the current level,\n",
    "            #   by comparing the first and last col_index.\n",
    "            max_width = max(max_width, col_index - level_head_index + 1)\n",
    "\n",
    "        return max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        給一個 binary tree 的 root\n",
    "        回傳在所有 level 中的最大寬度\n",
    "        width: \n",
    "        1. 在某一列(level)的最左邊 node(不是null) ~ 最右邊 node(不是null)\n",
    "        2. 在這兩個端點中如果有 null, 那也把它加入計算\n",
    "        \"\"\"\n",
    "        \n",
    "        # 在 node = null 的狀況下, 做一個\"假的 node\"(會超時)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        max_len = 0\n",
    "        \n",
    "        while q:\n",
    "            result = []\n",
    "            #print(f\"{q=}\")\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "                else:\n",
    "                    node = TreeNode(val=101)\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            left  = 0\n",
    "            right = len(result) - 1\n",
    "            while left <= right:\n",
    "                if result[left] == 101:\n",
    "                    left  += 1\n",
    "                elif result[right] == 101:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    max_len = max(max_len, right - left + 1)\n",
    "                    break\n",
    "            \n",
    "            count = 0\n",
    "            for i in range(len(q)):\n",
    "                if not q[i]:\n",
    "                    count += 1\n",
    "            if count == len(q):\n",
    "                break\n",
    "        return max_len\n",
    "        \"\"\"\n",
    "        \n",
    "        # 給每個 node 都打上 count (太難了想不到...)\n",
    "        \"\"\"\n",
    "             1 (假設 root 是 count 1)\n",
    "            / \\\n",
    "           2   3\n",
    "           root.left  的記號是 count * 2\n",
    "           root.right 的記號是 (count * 2) + 1\n",
    "        \n",
    "        在每一層結束的時候, 計算 result[-1] - result[0] + 1\n",
    "        這就是那一層的最大寬度\n",
    "        \"\"\"\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        \n",
    "        max_len = 0\n",
    "        while q:\n",
    "            result = []\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node:\n",
    "                    result.append(count)\n",
    "                    q.append([node.left,  (count * 2)])\n",
    "                    q.append([node.right, (count * 2) + 1])\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            if result:\n",
    "                max_len = max(max_len, result[-1] - result[0] + 1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        l = []\n",
    "        l.append([root,0])\n",
    "        ans = 0\n",
    "        while l:\n",
    "           \n",
    "            ans = max(ans,l[-1][1]-l[0][1]+1)\n",
    "            for i in range(len(l)):\n",
    "                    r = l.pop(0)\n",
    "                    print(r[1])\n",
    "                    if r[0].left:\n",
    "                        l.append([r[0].left,r[1]*2])\n",
    "                    if r[0].right:\n",
    "                        l.append([r[0].right,r[1]*2+1])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        給一個 binary tree 的 root\n",
    "        回傳在所有 level 中的最大寬度\n",
    "        width: \n",
    "        1. 在某一列(level)的最左邊 node(不是null) ~ 最右邊 node(不是null)\n",
    "        2. 在這兩個端點中如果有 null, 那也把它加入計算\n",
    "        \"\"\"\n",
    "        \n",
    "        # 在 node = null 的狀況下, 做一個\"假的 node\"(會超時)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        max_len = 0\n",
    "        \n",
    "        while q:\n",
    "            result = []\n",
    "            #print(f\"{q=}\")\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "                else:\n",
    "                    node = TreeNode(val=101)\n",
    "                    result.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            left  = 0\n",
    "            right = len(result) - 1\n",
    "            while left <= right:\n",
    "                if result[left] == 101:\n",
    "                    left  += 1\n",
    "                elif result[right] == 101:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    max_len = max(max_len, right - left + 1)\n",
    "                    break\n",
    "            \n",
    "            count = 0\n",
    "            for i in range(len(q)):\n",
    "                if not q[i]:\n",
    "                    count += 1\n",
    "            if count == len(q):\n",
    "                break\n",
    "        return max_len\n",
    "        \"\"\"\n",
    "        count = 1\n",
    "        q = collections.deque()\n",
    "        q.append([root, count])\n",
    "        max_len = 0\n",
    "        while q:\n",
    "            result = []\n",
    "            for i in range(len(q)):\n",
    "                node, count = q.popleft()\n",
    "                if node:\n",
    "                    result.append(count)\n",
    "                    q.append([node.left,  (count * 2)])\n",
    "                    q.append([node.right, (count * 2) + 1])\n",
    "            \n",
    "            print(f\"{result=}\")\n",
    "            if result:\n",
    "                max_len = max(max_len, result[-1] - result[0] + 1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        nodequeue = [0 for _ in range(3001)]\n",
    "        idqueue = [0 for _ in range(3001)]\n",
    "        l = r = 0\n",
    "        nodequeue[r] = root\n",
    "        idqueue[r] = 1\n",
    "        r += 1\n",
    "        ans = 1\n",
    "        while l<r:\n",
    "            size = r-l\n",
    "            ans = max(ans, idqueue[r-1] - idqueue[l] + 1)\n",
    "            for i in range(size):\n",
    "                node = nodequeue[l]\n",
    "                id = idqueue[l]\n",
    "                l += 1\n",
    "                if node.left:\n",
    "                    nodequeue[r] = node.left\n",
    "                    idqueue[r] = 2*id\n",
    "                    r += 1\n",
    "                if node.right:\n",
    "                    nodequeue[r] = node.right\n",
    "                    idqueue[r] = 2*id+1\n",
    "                    r += 1\n",
    "           \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 1\n",
    "        nodequeue = [0]*3001\n",
    "        idqueue = [0]*3001\n",
    "        l = 0\n",
    "        r = 0\n",
    "        nodequeue[r] = root\n",
    "        idqueue[r] = 1\n",
    "        r += 1\n",
    "        while l<r:\n",
    "            size = r-l\n",
    "            ans = max(ans,idqueue[r-1]-idqueue[l]+1)\n",
    "            for i in range(size):\n",
    "                cur = nodequeue[l]\n",
    "                value = idqueue[l]\n",
    "                l += 1\n",
    "                if cur.left:\n",
    "                    nodequeue[r] = cur.left\n",
    "                    idqueue[r] = 2*value\n",
    "                    r += 1\n",
    "                if cur.right:\n",
    "                    nodequeue[r] = cur.right\n",
    "                    idqueue[r] = 2*value+1\n",
    "                    r += 1\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        max_size = 3001\n",
    "        nq = [0] * max_size # nq: 节点队列\n",
    "        iq = [0] * max_size # iq: 节点编号队列\n",
    "        nq[0], iq[0] = root, 1\n",
    "        L, R = 0, 1\n",
    "        while L < R:\n",
    "            size = R - L \n",
    "            ans = max(ans, iq[R-1] - iq[L] + 1)\n",
    "            for _ in range(size):\n",
    "                cur = nq[L]\n",
    "                idx = iq[L]\n",
    "                L += 1\n",
    "                if cur.left is not None:\n",
    "                    nq[R] = cur.left\n",
    "                    iq[R] = 2 * idx\n",
    "                    R += 1\n",
    "                if cur.right is not None:\n",
    "                    nq[R] = cur.right\n",
    "                    iq[R] = 2 * idx + 1\n",
    "                    R += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append([root, 1, 1])\n",
    "        ans = []\n",
    "        while queue:\n",
    "            p, layer, index = queue.popleft()\n",
    "            if layer>len(ans):\n",
    "                ans.append([index])\n",
    "            else:\n",
    "                ans[layer-1].append(index)\n",
    "            if p.left:\n",
    "                queue.append([p.left, layer+1, 2*index])\n",
    "            if p.right:\n",
    "                queue.append([p.right, layer+1, 2*index+1])\n",
    "        return max(a[-1]-a[0]+1 for a in ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        node_que = [None] * 3001\n",
    "        id_que = [0] * 3001\n",
    "        l, r = 0, 0\n",
    "        ans = 1\n",
    "        node_que[r] = root\n",
    "        id_que[r] = 1\n",
    "        r += 1\n",
    "\n",
    "        while l < r:\n",
    "            size = r - l\n",
    "            ans = max(ans, id_que[r-1] - id_que[l] + 1)\n",
    "            for i in range(size):\n",
    "                node = node_que[l]\n",
    "                node_id = id_que[l]\n",
    "                l += 1\n",
    "                if node.left is not None:\n",
    "                    node_que[r] = node.left\n",
    "                    id_que[r] = node_id * 2\n",
    "                    r += 1\n",
    "                if node.right is not None:\n",
    "                    node_que[r] = node.right\n",
    "                    id_que[r] =  node_id * 2 + 1\n",
    "                    r += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        deq = deque()\n",
    "        deq.append(root)\n",
    "        lookUp = dict()\n",
    "        lookUp[root] = 1\n",
    "        res = 1\n",
    "        while len(deq) > 0:\n",
    "            size = len(deq)\n",
    "            minimum = float('inf')\n",
    "            maxium = -float('inf')\n",
    "            while size > 0:\n",
    "                size -= 1\n",
    "                node = deq.popleft()\n",
    "                index = lookUp[node]\n",
    "                if node.left:\n",
    "                    deq.append(node.left)\n",
    "                    lookUp[node.left] = 2 * index - 1\n",
    "                if node.right:\n",
    "                    deq.append(node.right)\n",
    "                    lookUp[node.right] = 2 * index \n",
    "                minimum = min(minimum, index)\n",
    "                maxium = max(maxium, index)\n",
    "            res = max(res, maxium - minimum + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res=1\n",
    "        root.val=1\n",
    "        queue = collections.deque([root, None])\n",
    "        candidate=[]\n",
    "\n",
    "        while len(queue)>1:\n",
    "            cur=queue.popleft()\n",
    "            if cur:\n",
    "                if len(candidate)==0 or len(candidate)==1:\n",
    "                    candidate.append(cur.val)\n",
    "                else:\n",
    "                    candidate.pop()\n",
    "                    candidate.append(cur.val)\n",
    "\n",
    "                if cur.left:\n",
    "                    cur.left.val=cur.val*2-1\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    cur.right.val=cur.val*2\n",
    "                    queue.append(cur.right)\n",
    "\n",
    "            else:\n",
    "                if len(candidate)==2:\n",
    "                    self.res=max(self.res, candidate[1]-candidate[0]+1)\n",
    "                candidate=[]\n",
    "                queue.append(None)\n",
    "        if len(candidate)==2:\n",
    "            self.res=max(self.res, candidate[1]-candidate[0]+1)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        level_info = {}\n",
    "        queue = [(root, 1, 1)] # node, level, index\n",
    "        while queue:\n",
    "            node, level, index = queue.pop(0)\n",
    "            if level not in level_info:\n",
    "                level_info[level] = [index]\n",
    "            else:\n",
    "                level_info[level].append(index)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1, index * 2))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1, index * 2 + 1))\n",
    "        # level_info = sorted(level_info.items(), key=lambda x: -x[0])\n",
    "        # print(level_info)\n",
    "        res = 0\n",
    "        for level, index_list in level_info.items():\n",
    "            res = max(res, max(index_list) - min(index_list) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        level_info = {}\n",
    "        queue = [(root, 1, 1)] # node, level, index\n",
    "        while queue:\n",
    "            node, level, index = queue.pop(0)\n",
    "            if level not in level_info:\n",
    "                level_info[level] = [index]\n",
    "            else:\n",
    "                level_info[level].append(index)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1, index * 2))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1, index * 2 + 1))\n",
    "        # level_info = sorted(level_info.items(), key=lambda x: -x[0])\n",
    "        # print(level_info)\n",
    "        res = 0\n",
    "        for level, index_list in level_info.items():\n",
    "            res = max(res, max(index_list) - min(index_list) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        level_info = {}\n",
    "        queue = [(root, 1, 1)] # node, level, index\n",
    "        while queue:\n",
    "            node, level, index = queue.pop(0)\n",
    "            if level not in level_info:\n",
    "                level_info[level] = [index]\n",
    "            else:\n",
    "                level_info[level].append(index)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1, index * 2))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1, index * 2 + 1))\n",
    "        # level_info = sorted(level_info.items(), key=lambda x: -x[0])\n",
    "        # print(level_info)\n",
    "        res = 0\n",
    "        for level, index_list in level_info.items():\n",
    "            res = max(res, max(index_list) - min(index_list) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def widthOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 0\n",
    "        nodes = []\n",
    "        queue = [[root,1,1]]\n",
    "        depth_now = 0\n",
    "        tmp = []\n",
    "        while queue != []:\n",
    "            node,idx,depth = queue.pop(0)\n",
    "            if depth != depth_now:\n",
    "                depth_now = depth\n",
    "                if tmp != []:\n",
    "                    nodes.append(tmp)\n",
    "                    tmp = []\n",
    "            if node is None:\n",
    "                continue\n",
    "            else:\n",
    "                tmp.append(idx)\n",
    "                queue.append([node.left,idx*2,depth+1])\n",
    "                queue.append([node.right,idx*2+1,depth+1])\n",
    "        maxn = 0\n",
    "        for n in nodes:\n",
    "            maxn = max(maxn,n[-1]-n[0]+1)\n",
    "        return maxn "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        level_info = {}\n",
    "        queue = [(root, 1, 1)] # node, level, index\n",
    "        while queue:\n",
    "            node, level, index = queue.pop(0)\n",
    "            if level not in level_info:\n",
    "                level_info[level] = [index]\n",
    "            else:\n",
    "                level_info[level].append(index)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1, index * 2))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1, index * 2 + 1))\n",
    "        # level_info = sorted(level_info.items(), key=lambda x: -x[0])\n",
    "        # print(level_info)\n",
    "        res = 0\n",
    "        for level, index_list in level_info.items():\n",
    "            res = max(res, max(index_list) - min(index_list) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def bfs(root):\n",
    "            q = collections.deque()\n",
    "            q.append((root, 0, 0))\n",
    "            dictw = defaultdict(list)\n",
    "\n",
    "            while len(q) > 0 :\n",
    "                u, wid, dep = q.popleft()\n",
    "                dictw[dep].append(wid)\n",
    "                if u.left: \n",
    "                    q.append((u.left, wid * 2, dep+1))\n",
    "                if u.right: \n",
    "                    q.append((u.right, wid * 2 + 1, dep+1))\n",
    "            \n",
    "            return dictw\n",
    "        \n",
    "        dictw = bfs(root)\n",
    "        res = 0\n",
    "        for wlist in dictw.values():\n",
    "            res = max(res, max(wlist) - min(wlist) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, head: Optional[TreeNode]) -> int:\n",
    "        if head is None:\n",
    "            return 0\n",
    "        dic={}\n",
    "        dic[head]=(0,0)  ##层数,标记\n",
    "        my_deque=deque()\n",
    "        my_deque.append(head)\n",
    "        curlevel=0\n",
    "        reslevel=0\n",
    "        resStart=0\n",
    "        res=0\n",
    "        while len(my_deque) >0:\n",
    "            head=my_deque.popleft()\n",
    "            if curlevel !=dic[head][0]:\n",
    "                res=max(reslevel,res)\n",
    "                reslevel=1\n",
    "                resStart=dic[head][1]\n",
    "                curlevel+=1\n",
    "            else:\n",
    "                reslevel=dic[head][1]-resStart+1\n",
    "            \n",
    "            if head.left is not None:\n",
    "                my_deque.append(head.left)\n",
    "                dic[head.left]=(dic[head][0]+1,dic[head][1]*2+1)\n",
    "            if head.right is not None:\n",
    "                my_deque.append(head.right)\n",
    "                dic[head.right]=(dic[head][0]+1,dic[head][1]*2+2)\n",
    "        res=max(reslevel,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        dict_mm = collections.defaultdict(list)\n",
    "        queue = [(root, 0, 1)] # 深度，编号\n",
    "        while queue:\n",
    "            node, depth, index = queue.pop(0)\n",
    "            if node:\n",
    "                dict_mm[depth].append(index)\n",
    "                queue.append((node.left, depth+1, 2*index))\n",
    "                queue.append((node.right, depth+1, 2*index+1))\n",
    "        ans = 0\n",
    "        for i in range(depth):\n",
    "            ans = max(ans, dict_mm[i][-1]-dict_mm[i][0]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "from collections import defaultdict\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        level_info = {}\n",
    "        queue = [(root, 1, 1)] # node, level, index\n",
    "        while queue:\n",
    "            node, level, index = queue.pop(0)\n",
    "            if level not in level_info:\n",
    "                level_info[level] = [index]\n",
    "            else:\n",
    "                level_info[level].append(index)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1, index * 2))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1, index * 2 + 1))\n",
    "        level_info = sorted(level_info.items(), key=lambda x: -x[0])\n",
    "        res = 0\n",
    "        for level, index_list in level_info:\n",
    "            res = max(res, max(index_list) - min(index_list) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if root is None: return 0\n",
    "        cur = [root]\n",
    "        maxWidth = 1\n",
    "        while True:\n",
    "            nxt = []\n",
    "            for node in cur:\n",
    "                if node is None:\n",
    "                    nxt.extend([None]*2)\n",
    "                else:\n",
    "                    nxt.append(node.left)\n",
    "                    nxt.append(node.right)\n",
    "            l = 0; r = len(nxt)-1\n",
    "            while l<len(nxt) and nxt[l] is None:\n",
    "                l += 1\n",
    "            while r>=0 and nxt[r] is None:\n",
    "                r -= 1\n",
    "            if l>=len(nxt) or r<0 or l>r:\n",
    "                break\n",
    "            maxWidth = max(maxWidth, r-l+1)\n",
    "\n",
    "            cur = nxt[l:r+1]\n",
    "        return maxWidth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        floor = list()\n",
    "        floor_1 = list()\n",
    "        self.get_tree(root, floor, floor_1, 1, 1)\n",
    "        return max(floor)\n",
    "    \n",
    "    def get_tree(self, root, floor, floor_1, i, num):\n",
    "        if i <= len(floor):\n",
    "            if num - floor_1[i - 1] + 1> floor[i -1]:\n",
    "                floor[i-1] = num - floor_1[i - 1] + 1\n",
    "        else:\n",
    "            floor.append(1)\n",
    "            floor_1.append(num)\n",
    "        if root.left:\n",
    "            self.get_tree(root.left, floor, floor_1, i+1, num * 2 -1)\n",
    "        # elif root.right:\n",
    "        #     if i <= len(floor):\n",
    "        #         if num > floor[i - 1]:\n",
    "        #             floor[i] = num\n",
    "        #     else:\n",
    "        #         floor.append(num)\n",
    "        if root.right:\n",
    "            self.get_tree(root.right, floor, floor_1, i+1, num * 2)\n",
    "        # elif root.left:\n",
    "        #     if i <= len(floor):\n",
    "        #         if num > floor[i - 1]:\n",
    "        #             floor[i] = num\n",
    "        #     else:\n",
    "        #         floor.append(num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def indexOfBinaryTree(self, root: TreeNode, val: int, index: List[int]):\n",
    "        # to find the left of left-tree and right of right-tree\n",
    "        if not root:\n",
    "            return\n",
    "        index.append(val)\n",
    "        if root.right:\n",
    "            self.indexOfBinaryTree(root.right, val * 2 + 1, index)\n",
    "        if root.left:\n",
    "            self.indexOfBinaryTree(root.left, val * 2, index)\n",
    "\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        # to find the left of left-tree and right of right-tree\n",
    "        if not root:\n",
    "            return 0\n",
    "        index = []\n",
    "        self.indexOfBinaryTree(root, 1, index)\n",
    "        index = sorted(index)\n",
    "        pos = 0\n",
    "        n = len(index)\n",
    "        level = 0\n",
    "        res = 1\n",
    "        left = 1\n",
    "        while pos < n:\n",
    "            if index[pos] >= 2 << level:\n",
    "                level += 1\n",
    "                if pos > 0:\n",
    "                    res = max(res, index[pos - 1] - left + 1)\n",
    "                left = index[pos]\n",
    "            pos += 1\n",
    "        # last level\n",
    "        res = max(res, index[-1] - left + 1)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.tree = []\n",
    "        def dfs(root, level, index):\n",
    "            if not root:\n",
    "                return\n",
    "            if level == len(self.tree):\n",
    "                self.tree.append([index, index])\n",
    "            self.tree[level][0] = min(self.tree[level][0], index)\n",
    "            self.tree[level][1] = max(self.tree[level][1], index)\n",
    "            dfs(root.left, level + 1, index * 2)\n",
    "            dfs(root.right, level + 1, index * 2 + 1)\n",
    "        res = 0\n",
    "        dfs(root, 0, 0)\n",
    "        print(self.tree)\n",
    "        for a, b in self.tree:\n",
    "            res = max(res, b - a + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        memo = {}\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root, depth, u):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return\n",
    "            if depth not in memo:\n",
    "                memo[depth] = u\n",
    "            ans = max(ans, u-memo[depth]+1)\n",
    "            u = u-memo[depth]+1\n",
    "            dfs(root.left, depth+1, u<<1)\n",
    "            dfs(root.right, depth+1, u<<1|1)\n",
    "\n",
    "        dfs(root, 0, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def get_height(self, root):\n",
    "        if root is None:\n",
    "            return -1\n",
    "        left = self.get_height(root.left)\n",
    "        right = self.get_height(root.right)\n",
    "        return max(left, right) + 1\n",
    "\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        '''\n",
    "            1\n",
    "        3       2\n",
    "    5\n",
    "        '''\n",
    "        if root is None:\n",
    "            return 0\n",
    "        height = self.get_height(root)\n",
    "        dq = deque([(root, 0)])\n",
    "        result = 0\n",
    "        row = 0\n",
    "        while len(dq) != 0:\n",
    "            i, n = 0, len(dq)\n",
    "            tmp_nodes = list()\n",
    "            while i < n:\n",
    "                node = dq.popleft()\n",
    "                tmp_nodes.append(node)\n",
    "                if node[0].left:\n",
    "                    dq.append((node[0].left, node[1]-2**(height-row-1)))\n",
    "                if node[0].right:\n",
    "                    dq.append((node[0].right, node[1]+2**(height-row-1)))\n",
    "                i += 1\n",
    "            print(row, tmp_nodes[-1][1], tmp_nodes[0][1])\n",
    "            result = max(result, (tmp_nodes[-1][1] - tmp_nodes[0][1])//2**(height-row+1) + 1)\n",
    "            row += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        cur_depth = left = 0\n",
    "        queue = [(root, 0, 0)]\n",
    "        for node, depth, pos in queue:\n",
    "            if node:\n",
    "                queue.append((node.left, depth + 1, pos * 2 + 1))\n",
    "                queue.append((node.right, depth + 1, pos * 2 + 2))\n",
    "                if depth != cur_depth:\n",
    "                    cur_depth = depth\n",
    "                    left = pos\n",
    "                res = max(res, pos - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 662. Maximum Width of Binary Tree\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ids = []\n",
    "        def dfs(node: TreeNode, d: int, id: int) -> int:\n",
    "            if not node: return 0\n",
    "            if d == len(ids): ids.append(id)\n",
    "            return max(id - ids[d] + 1, \n",
    "                        dfs(node.left, d + 1, (id - ids[d]) * 2),\n",
    "                        dfs(node.right, d + 1, (id - ids[d]) * 2 + 1))\n",
    "        return dfs(root, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def _dfs(res,k,root,m):\n",
    "            if root is None:\n",
    "                return None\n",
    "            _dfs(res,k+1,root.right,m*2-1)\n",
    "            res.append([k,m])\n",
    "            _dfs(res,k+1,root.left,m*2)\n",
    "        _dfs(res,0,root,1)\n",
    "        res.sort(key = lambda x:-x[0])\n",
    "        a = 0\n",
    "        for k in range(res[0][0],-1,-1):\n",
    "            arr = [res[i] for i in range(len(res)) if res[i][0]==k]\n",
    "            a = max(a,arr[-1][1]-arr[0][1]+1)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, level, idx):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if level == len(levelMinIdx):\n",
    "                levelMinIdx.append(idx)\n",
    "            return max(\n",
    "                idx - levelMinIdx[level] + 1,\n",
    "                dfs(root.left, level + 1, 2 * (idx - levelMinIdx[level]) + 1),\n",
    "                dfs(root.right, level + 1, 2 * (idx - levelMinIdx[level]) + 2)\n",
    "            )\n",
    "\n",
    "        levelMinIdx = []\n",
    "        return dfs(root, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        dep_width = {}\n",
    "\n",
    "        def dfs(root, tid, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if not dep_width.get(depth):\n",
    "                dep_width.update({depth: tid})\n",
    "            nonlocal ans\n",
    "            ans = max(ans, tid - dep_width.get(depth) + 1)\n",
    "            tid = tid - dep_width.get(depth) + 1\n",
    "            dfs(root.left, tid << 1, depth + 1)\n",
    "            dfs(root.right, tid << 1 | 1, depth + 1)\n",
    "\n",
    "        dfs(root, 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 思路：给每层的每个节点加个位置信息\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_most_map = {}\n",
    "        ans = 0\n",
    "\n",
    "        # 先序遍历，根左右，每层第一个遍历到的即为该层的 left_most\n",
    "        def dfs(node: Optional[TreeNode], depth: int, idx: int) -> None:\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            if depth not in left_most_map:\n",
    "                left_most_map[depth] = idx\n",
    "            nonlocal ans\n",
    "            ans = max(ans, idx - left_most_map[depth] + 1)\n",
    "\n",
    "            dfs(node.left, depth + 1, 2 * (idx - left_most_map[depth]) + 1)\n",
    "            dfs(node.right, depth + 1, 2 * (idx - left_most_map[depth]) + 2)\n",
    "\n",
    "\n",
    "\n",
    "        dfs(root, 0, 0)\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.depthMap = {}\n",
    "        self.res = 0\n",
    "        self.dfs(root, 1, 0)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode], u:int, depth:int):\n",
    "        \n",
    "        if root is None:\n",
    "            return\n",
    "        # print(u, root.val, depth)            \n",
    "        if depth not in self.depthMap:\n",
    "            self.depthMap[depth] = u                    \n",
    "        self.res = max(self.res, u - self.depthMap[depth] + 1)            \n",
    "        u = u - self.depthMap[depth] + 1\n",
    "        self.dfs(root.left, u*2, depth+1)\n",
    "        self.dfs(root.right, u*2+1, depth+1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        dep_width = {}\n",
    "\n",
    "        def dfs(root, tid, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if not dep_width.get(depth):\n",
    "                dep_width.update({depth: tid})\n",
    "            nonlocal ans\n",
    "            ans = max(ans, tid - dep_width.get(depth) + 1)\n",
    "            tid = tid - dep_width.get(depth) + 1\n",
    "            dfs(root.left, tid << 1, depth + 1)\n",
    "            dfs(root.right, tid << 1 | 1, depth + 1)\n",
    "\n",
    "        dfs(root, 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.depthfirst = dict()\n",
    "        self.ans = 0\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root, 1, 0)\n",
    "        return self.ans \n",
    "    def dfs(self, root, u, depth):\n",
    "        if not root:\n",
    "            return \n",
    "        if depth not in self.depthfirst:\n",
    "            self.depthfirst[depth] = u \n",
    "            # 字典里放最左的节点的编号，u是最右（或者最后一次被循环到的节点的编号， 右节点 - 左节点 + 1）\n",
    "        self.ans = max(self.ans, u - self.depthfirst[depth] + 1)\n",
    "        u = u - self.depthfirst.get(depth) + 1;\n",
    "        self.dfs(root.left, u << 1, depth + 1)\n",
    "        self.dfs(root.right, u << 1 | 1, depth + 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        root.val=1\n",
    "        def valstd(root):\n",
    "            if root.left:\n",
    "                root.left.val=2*root.val\n",
    "                valstd(root.left)\n",
    "            if root.right:\n",
    "                root.right.val=2*root.val+1\n",
    "                valstd(root.right)\n",
    "        valstd(root)\n",
    "        from queue import Queue \n",
    "        q=Queue()\n",
    "        lvl=1\n",
    "        q.put(root)\n",
    "        rv=lv=1\n",
    "        ans=0\n",
    "        while not q.empty():\n",
    "            r=q.get()\n",
    "            v=r.val\n",
    "            if v<2**lvl:\n",
    "                rv=v\n",
    "            else:\n",
    "\n",
    "                lv=v\n",
    "                lvl+=1\n",
    "            ans=max(ans,rv-lv+1)\n",
    "            if r.left:\n",
    "                q.put(r.left)\n",
    "            if r.right:\n",
    "                q.put(r.right)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        l1=[root]\n",
    "        l2=[]\n",
    "        res=0\n",
    "        self.visit(root,0)\n",
    "        while l1:\n",
    "            res=max(res,l1[-1].val-l1[0].val+1)\n",
    "            l2=[]\n",
    "            for i in l1:\n",
    "                if i.left:\n",
    "                    l2.append(i.left)\n",
    "                if i.right:\n",
    "                    l2.append(i.right)\n",
    "            l1=l2\n",
    "\n",
    "        return res\n",
    "    def visit(self,root,val):\n",
    "        if root.left is not None:\n",
    "            self.visit(root.left,val*2)\n",
    "        if root.right is not None:\n",
    "            self.visit(root.right,val*2+1)\n",
    "        root.val=val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 将题给二叉树的节点值进行更改\n",
    "        def change_val(root):\n",
    "            if root.left:\n",
    "                root.left.val = root.val * 2\n",
    "                change_val(root.left)\n",
    "            if root.right:\n",
    "                root.right.val = root.val * 2 + 1\n",
    "                change_val(root.right)\n",
    "        \n",
    "        # 将二叉树的各层元素按层放置于一列表中\n",
    "        def layer_tree(root):\n",
    "            res = []  # 结果\n",
    "            if root :  \n",
    "                queue = [root]  # 第一层\n",
    "            else:\n",
    "                return res\n",
    "        \n",
    "            while len(queue):  # 当下一层没有子节点后停止遍历\n",
    "                n = len(queue)\n",
    "                r = []\n",
    "                for _ in range(n):\n",
    "                    node = queue.pop(0)  # 弹出第一个值\n",
    "                    r.append(node.val)\n",
    "                    if node.left:  # 左子树判断\n",
    "                        queue.append(node.left)\n",
    "                    if node.right:  # 右子树判断\n",
    "                        queue.append(node.right)\n",
    "                res.append(r)  # 加入一层的结果\n",
    "            return res\n",
    "        \n",
    "        change_val(root)\n",
    "        tree_layer = layer_tree(root)\n",
    "        ans = 0\n",
    "        for layer in tree_layer:\n",
    "            ans = max(ans, layer[-1] - layer[0] + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_width = 0\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        depth_dict = dict()\n",
    "        def dupFunc(node, val, lvl):\n",
    "            if node is None:\n",
    "                return\n",
    "            if lvl not in depth_dict:\n",
    "                depth_dict[lvl] = val\n",
    "            self.max_width = max(self.max_width, val - depth_dict[lvl] + 1)\n",
    "            val = val - depth_dict.get(lvl) + 1\n",
    "            dupFunc(node.left, val * 2, lvl + 1)\n",
    "            dupFunc(node.right, val * 2 + 1, lvl + 1)\n",
    "        dupFunc(root, 1, 0)\n",
    "        return self.max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_width = 0\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        depth_dict = dict()\n",
    "        def dupFunc(node, val, lvl):\n",
    "            if node is None:\n",
    "                return\n",
    "            if lvl not in depth_dict:\n",
    "                depth_dict[lvl] = val\n",
    "            self.max_width = max(self.max_width, val - depth_dict[lvl] + 1)\n",
    "            val = val - depth_dict.get(lvl) + 1\n",
    "            dupFunc(node.left, val << 1, lvl + 1)\n",
    "            dupFunc(node.right, val << 1 | 1, lvl + 1)\n",
    "        dupFunc(root, 1, 0)\n",
    "        print(depth_dict)\n",
    "        return self.max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_width = 0\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        depth_dict = dict()\n",
    "        def dupFunc(node, val, lvl):\n",
    "            if node is None:\n",
    "                return\n",
    "            if lvl not in depth_dict:\n",
    "                depth_dict[lvl] = val\n",
    "            self.max_width = max(self.max_width, val - depth_dict[lvl] + 1)\n",
    "            val = val - depth_dict.get(lvl) + 1\n",
    "            dupFunc(node.left, val << 1, lvl + 1)\n",
    "            dupFunc(node.right, val << 1 | 1, lvl + 1)\n",
    "        dupFunc(root, 1, 0)\n",
    "        print(depth_dict)\n",
    "        return self.max_width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = []\n",
    "        def dfs(root,height,index):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if height == len(ans):\n",
    "                ans.append(index)\n",
    "            return max(index-ans[height]+1,\n",
    "            dfs(root.left, height+1,index*2),\n",
    "            dfs(root.right, height+1,index*2+1))\n",
    "        return dfs(root,0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.firstId = [] #记录各层第一个不为空的节点的id\n",
    "        self.maxWidth = 1\n",
    "\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # dfs\n",
    "        if root == None:\n",
    "            return 0\n",
    "        self.traverse(root,1,1)\n",
    "        return self.maxWidth\n",
    "        \n",
    "    def traverse(self,root,depth,id):\n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        if len(self.firstId) == depth - 1:\n",
    "            # 第一层进入该层\n",
    "            self.firstId.append(id)\n",
    "        else:\n",
    "            #不是第一次进入该层，那就要维护maxWidth\n",
    "            self.maxWidth = max(self.maxWidth, id - self.firstId[depth-1] + 1)\n",
    "        \n",
    "        self.traverse(root.left, depth + 1, id*2)\n",
    "        self.traverse(root.right, depth + 1, id*2 + 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        # time O(n), space O(n)\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        book = dict()\n",
    "        def dfs(root, idx, level, book):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if level not in book:\n",
    "                book[level] = idx\n",
    "            else:\n",
    "                self.res = max(self.res, idx - book[level] + 1)\n",
    "            \n",
    "            dfs(root.left, idx * 2, level + 1, book)\n",
    "            dfs(root.right, idx * 2 + 1, level + 1, book)\n",
    "        \n",
    "        self.res = 1\n",
    "        \n",
    "        dfs(root, 1, 1, book)\n",
    "        \n",
    "        \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        levelMin = {}\n",
    "        def dfs(node, depth, index):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if depth not in levelMin:\n",
    "                levelMin[depth] = index  # 每层最左边的节点是最小的序号\n",
    "            return max(\n",
    "                        index-levelMin[depth]+1, \n",
    "                        dfs(node.left, depth+1, index*2), \n",
    "                        dfs(node.right, depth+1, index*2+1)\n",
    "                        )\n",
    "        return dfs(root, 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        map = dict()\n",
    "\n",
    "        def dfs(root: Optional[TreeNode], depth: int, index: int) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            if depth not in map.keys():\n",
    "                map[depth] = index\n",
    "            return max(index - map[depth] + 1, dfs(root.left, depth + 1, index * 2),\n",
    "                       dfs(root.right, depth + 1, index * 2 + 1))\n",
    "\n",
    "        return dfs(root, 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        levelMin = {}\n",
    "\n",
    "        def dfs(node: Optional[TreeNode], depth: int, index: int) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if depth not in levelMin:\n",
    "                levelMin[depth] = index\n",
    "            \n",
    "            return max(index - levelMin[depth] + 1, \n",
    "            dfs(node.left, depth + 1, index * 2),\n",
    "            dfs(node.right, depth + 1, index * 2 + 1))\n",
    "        return dfs(root, 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        def traversal(left, right, temp) -> None:\n",
    "            nonlocal res\n",
    "            if not left.left and not left.right and not right.left and not right.right:\n",
    "                return\n",
    "            else:\n",
    "                if left.left and right.right:\n",
    "                    a = temp * 2\n",
    "                    res = max(res, a)\n",
    "                    traversal(left.left, right.right, a)\n",
    "                if left.left and right.left:\n",
    "                    a = temp * 2 - 1\n",
    "                    res = max(res, a)\n",
    "                    traversal(left.left, right.left, a)\n",
    "                if left.right and right.right:\n",
    "                    a = temp * 2 - 1\n",
    "                    res = max(res, a)\n",
    "                    traversal(left.right, right.right, a)\n",
    "                if left.right and right.left:\n",
    "                    a = temp * 2 - 2\n",
    "                    res = max(res, a)\n",
    "                    traversal(left.right, right.left, a)\n",
    "                if not right.right and not right.left:\n",
    "                    if left.left and left.right:\n",
    "                        traversal(left.left, left.right, 1)\n",
    "                    elif left.left and not left.right:\n",
    "                        traversal(left.left, left.left, 1)\n",
    "                    elif not left.left and left.right:\n",
    "                        traversal(left.right, left.right, 1)\n",
    "                if not left.left and not left.right:\n",
    "                    if right.left and right.right:\n",
    "                        traversal(right.left, right.right, 1)\n",
    "                    elif right.left and not right.right:\n",
    "                        traversal(right.left, right.left, 1)\n",
    "                    elif not right.left and right.right:\n",
    "                        traversal(right.right, right.right, 1)\n",
    "        traversal(root, root, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.mi = [-1] * 3005\n",
    "\n",
    "        self.ans = 0\n",
    "        self.dfs(root, 0, 1)\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, root, deep, num):\n",
    "        if self.mi[deep] == -1:\n",
    "            self.mi[deep] = num\n",
    "        \n",
    "        self.ans = max(self.ans, num - self.mi[deep] + 1)\n",
    "        num = num - self.mi[deep] + 1\n",
    "\n",
    "        if root.left is not None:\n",
    "            self.dfs(root.left, deep+1, num*2)\n",
    "        if root.right is not None:\n",
    "            self.dfs(root.right, deep+1, num*2+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.map = dict()\n",
    "        self.ans = 0\n",
    "        self.dfs(root, 1, 0)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, root: TreeNode, u: int, depth: int):\n",
    "        if root is None:\n",
    "            return\n",
    "        if depth not in self.map:\n",
    "            self.map[depth] = u\n",
    "        self.ans = max(self.ans, u - self.map[depth] + 1)\n",
    "        u = u - self.map[depth] + 1\n",
    "        self.dfs(root.left, 2 * u, depth+1)\n",
    "        self.dfs(root.right, 2 * u + 1, depth+1)\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, num, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if depth not in map1:\n",
    "                map1[depth] = num\n",
    "            self.res = max(self.res, num - map1[depth] + 1)\n",
    "            num = num - map1[depth] + 1\n",
    "            dfs(root.left, num * 2, depth + 1)\n",
    "            dfs(root.right, num * 2 + 1, depth + 1)\n",
    "\n",
    "        map1 = {}\n",
    "        self.res = 0\n",
    "        dfs(root, 1, 0)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        cnt = {}\n",
    "        def dfs(root, u, depth):\n",
    "            if root is None: return\n",
    "            if depth not in cnt: cnt[depth] = u\n",
    "            nonlocal ans\n",
    "            ans = max(ans, u - cnt[depth] + 1)\n",
    "            u = u - cnt[depth] + 1\n",
    "            dfs(root.left, u << 1, depth + 1)\n",
    "            dfs(root.right, u << 1 | 1, depth + 1)\n",
    "        dfs(root, 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.record = {}\n",
    "        self.travel(root, 0, 0)\n",
    "        ans = 0\n",
    "        for k in self.record:\n",
    "            ans = max(ans, 1 + self.record[k][1] - self.record[k][0])\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    def travel(self, node, level, index):\n",
    "        if node == None:\n",
    "            return\n",
    "        if level not in self.record:\n",
    "            self.record[level] = [index, index]\n",
    "        else:\n",
    "            self.record[level][1] = index\n",
    "        self.travel(node.left, level+1, 2 * index + 1)\n",
    "        self.travel(node.right, level+1, 2 * index + 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        map={}\n",
    "        ans=0\n",
    "        def dfs(r,u,depth):\n",
    "            if r==None:\n",
    "                return\n",
    "            if depth not in map:\n",
    "                map[depth]=u\n",
    "            nonlocal ans\n",
    "            ans=max(ans,u-map[depth]+1)\n",
    "            u=u-map[depth]+1\n",
    "            dfs(r.left,u<<1,depth+1)\n",
    "            dfs(r.right,u<<1 | 1, depth+1)\n",
    "        dfs(root,1,0)\n",
    "        return ans\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        depth_map = collections.defaultdict(int)\n",
    "        def dfs(root, u, depth):\n",
    "            if root is None: return\n",
    "            if depth_map[depth] == 0:\n",
    "                depth_map[depth] = u\n",
    "            self.ans = max(self.ans, u - depth_map[depth] + 1)\n",
    "            u = u - depth_map[depth] + 1\n",
    "            dfs(root.left, u << 1, depth + 1)\n",
    "            dfs(root.right, u << 1 | 1, depth + 1)\n",
    "        dfs(root, 1, 0)\n",
    "        return self.ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        levels = []\n",
    "        def level_order(root: Optional[TreeNode], level: int, index: int):\n",
    "            if root is None:\n",
    "                return \n",
    "            if len(levels) <= level:\n",
    "                levels.append([])\n",
    "            levels[level].append(index)\n",
    "            level_order(root.left, level+1, index*2+1)\n",
    "            level_order(root.right, level+1, index*2+2)\n",
    "        \n",
    "        level_order(root, 0, 0)\n",
    "        \n",
    "        r = 0\n",
    "        for i in levels:\n",
    "            tmp = max(i) - min(i) + 1\n",
    "            if tmp > r:\n",
    "                r = tmp\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        left_right_each_layer = []\n",
    "        if root == None:\n",
    "            return 0\n",
    "        def dfs(root, layNum, id):\n",
    "            if root == None:\n",
    "                return\n",
    "            if len(left_right_each_layer) < layNum:\n",
    "                left_right_each_layer.append([id, id])\n",
    "            else:\n",
    "                left_right_each_layer[layNum-1][1] = id\n",
    "            dfs(root.left, layNum+1, 2*id)\n",
    "            dfs(root.right, layNum+1, 2*id+1)\n",
    "        \n",
    "        dfs(root, 1, 1)\n",
    "        # print(left_right_each_layer)\n",
    "        res = 0\n",
    "        for l, r in left_right_each_layer:\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        def mark(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if root.left:\n",
    "                root.left.val = 2 * root.val\n",
    "            if root.right:\n",
    "                root.right.val = 2 * root.val + 1\n",
    "            \n",
    "            mark(root.left)\n",
    "            mark(root.right)\n",
    "\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        root.val = 1\n",
    "        mark(root)\n",
    "\n",
    "\n",
    "        ll = [root]\n",
    "        tmp = []\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        while ll:\n",
    "            node = ll.pop(0)\n",
    "            if node.left:\n",
    "                tmp.append(node.left)\n",
    "            if node.right:\n",
    "                tmp.append(node.right)\n",
    "\n",
    "            if not ll and tmp:\n",
    "                ans = max(tmp[-1].val - tmp[0].val + 1, ans)\n",
    "                ll.extend(tmp)\n",
    "                tmp.clear()\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        leftest = []\n",
    "        level = 0\n",
    "        max_with = [0]\n",
    "        cur_pos = 0\n",
    "\n",
    "        def cal_pos(array):\n",
    "            pos = 0\n",
    "            for i in range(len(array)):\n",
    "                if array[i] == 0:\n",
    "                    pos = 2 * (pos) + 1\n",
    "                else:\n",
    "                    pos = 2 * (pos)\n",
    "            return pos\n",
    "\n",
    "        def travel(node):\n",
    "            nonlocal level\n",
    "            nonlocal leftest\n",
    "            nonlocal cur_pos\n",
    "            if not node:\n",
    "                return\n",
    "            if max_with == 0:\n",
    "                cur_pos = 0\n",
    "            if level == len(leftest):\n",
    "                leftest.append(cur_pos)\n",
    "            level += 1\n",
    "            cur_pos *= 2\n",
    "            travel(node.left)\n",
    "            level -= 1\n",
    "            cur_pos //= 2\n",
    "            if level < len(leftest):\n",
    "\n",
    "                width = cur_pos - leftest[level]\n",
    "                if width >= max_with[0]:\n",
    "                    max_with[0] = width\n",
    "            level += 1\n",
    "            cur_pos = cur_pos * 2 + 1\n",
    "            travel(node.right)\n",
    "            level -= 1\n",
    "            cur_pos = (cur_pos-1) // 2\n",
    "\n",
    "        travel(root)\n",
    "        return int(max_with[0]) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 将这棵树编号,根节点编号x，那么左孩子就是2*x,右孩子编号是2*x+1\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        # self.width = 0\n",
    "        self.max_width = 1\n",
    "\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "       self.dfs(root,1,1) # 根节点，编号1，当前层数1\n",
    "       return self.max_width\n",
    "\n",
    "    def dfs(self,root,id,depth):\n",
    "        if not root:\n",
    "            return\n",
    "        # 先把左侧节点编号\n",
    "        if len(self.res)== (depth-1): # 这就是只会记录最左侧节点的Index，放进列表里\n",
    "            self.res.append(id)\n",
    "        else:\n",
    "            self.max_width = max(self.max_width,id-self.res[depth-1]+1)\n",
    "        self.dfs(root.left,2*id,depth+1)\n",
    "        self.dfs(root.right,2*id+1,depth+1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        # 保存每一层的最左i 以及最右 i\n",
    "        left = []\n",
    "        right = []\n",
    "\n",
    "        def dfs(node, depth, ix):\n",
    "            if len(left) < depth:\n",
    "                left.append(ix)\n",
    "                right.append(ix)\n",
    "            else:\n",
    "                right[depth-1] = ix\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left, depth+1, ix*2)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth+1, ix*2+1)\n",
    "\n",
    "        dfs(root, 1, 1)\n",
    "\n",
    "        maxw = 0\n",
    "        for i in range(len(left)):\n",
    "            maxw = max(maxw, right[i] - left[i] + 1)\n",
    "        return maxw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, level_min = 1, []\n",
    "        def dfs(node: TreeNode, depth: int, index: int):\n",
    "            if not node:\n",
    "                return \n",
    "            if len(level_min) == depth:\n",
    "                level_min.append(index)\n",
    "            else:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, index - level_min[depth] + 1)\n",
    "            dfs(node.left, depth + 1, index * 2)\n",
    "            dfs(node.right, depth + 1, index * 2 + 1)\n",
    "        \n",
    "        dfs(root, 0, 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        max_wide = 0\n",
    "        lable_num = 1\n",
    "        depth = 0\n",
    "        res = []\n",
    "        path = []\n",
    "        \n",
    "        def dfs(root, depth, lable_num):\n",
    "            nonlocal max_wide\n",
    "            if not root:\n",
    "                return\n",
    "            if depth == len(path):\n",
    "                path.append(lable_num)\n",
    "            else:\n",
    "                wide = lable_num - path[depth] + 1\n",
    "                max_wide = max(max_wide, lable_num - path[depth] + 1)\n",
    "            dfs(root.left, depth + 1, lable_num * 2)\n",
    "            dfs(root.right, depth + 1, lable_num * 2 + 1)\n",
    "        dfs(root, depth, lable_num)\n",
    "        return 1 if max_wide == 0 else max_wide\n",
    "                \n",
    "        \n",
    "        # 层序遍历\n",
    "        # q = collections.deque()\n",
    "        # q.append((root, 1))\n",
    "        # res = float('-inf')\n",
    "        # while q:\n",
    "        #     size = len(q)\n",
    "        #     path = []\n",
    "        #     for _ in range(size):\n",
    "        #         node, lable = q.popleft()\n",
    "        #         path.append(lable)\n",
    "        #         if node.left:\n",
    "        #             q.append((node.left, lable * 2))\n",
    "        #         if node.right:\n",
    "        #             q.append((node.right, lable * 2 + 1))\n",
    "        #     res = max(res, path[-1] - path[0] + 1)\n",
    "        # return res\n",
    "    \n",
    "        # # DFS遍历\n",
    "        # cnt = collections.defaultdict(list)\n",
    "        # res = float('-inf')\n",
    "        # def dfs(root, num, depth):\n",
    "        #     if not root:\n",
    "        #         return\n",
    "        #     cnt[depth].append(num)\n",
    "        #     dfs(root.left, num * 2, depth + 1)\n",
    "        #     dfs(root.right, num * 2 + 1, depth + 1)\n",
    "        #\n",
    "        # dfs(root, 1, 0)\n",
    "        # for node, val in cnt.items():\n",
    "        #     res = max(max(val) - min(val) + 1, res)\n",
    "        # return res\n",
    "        \n",
    "        # BFS\n",
    "        # q = collections.deque()\n",
    "        # q.append((root, 1))\n",
    "        # res = float('-inf')\n",
    "        # while q:\n",
    "        #     size = len(q)\n",
    "        #     for i in range(size):\n",
    "        #         node, lable_num = q.popleft()\n",
    "        #         if i == 0:\n",
    "        #             start_id = lable_num\n",
    "        #         if i + 1 == size:\n",
    "        #             end_id = lable_num\n",
    "        #         if node.left:\n",
    "        #             q.append((node.left, lable_num * 2))\n",
    "        #         if node.right:\n",
    "        #             q.append(((node.right, lable_num *2 + 1)))\n",
    "        #     res = max(res, end_id - start_id + 1)\n",
    "        # return res\n",
    "        \n",
    "        # dfs\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # res = float('-inf')\n",
    "        # first_id = []\n",
    "        # def dfs(root, lable_num, depth):\n",
    "        #     nonlocal res\n",
    "        #     if not root:\n",
    "        #         return\n",
    "        #     if depth == len(first_id):\n",
    "        #         first_id.append(lable_num)\n",
    "        #     else:\n",
    "        #         res = max(res, lable_num - first_id[depth] + 1)\n",
    "        #     dfs(root.left, lable_num * 2, depth + 1)\n",
    "        #     dfs(root.right, lable_num * 2 + 1, depth + 1)\n",
    "        # dfs(root, 1, 0)\n",
    "        # # 需要考虑仅为根节点时的情况\n",
    "        # return res if res != float('-inf') else 1\n",
    "        #\n",
    "        \n",
    "    \n",
    "            \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "\n",
    "        leftest = {}\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node, depth, idx):\n",
    "            nonlocal res\n",
    "\n",
    "            if depth in leftest:\n",
    "                leftest[depth] = min(leftest[depth], idx)\n",
    "            else:\n",
    "                leftest[depth] = idx\n",
    "            \n",
    "            res = max(res, idx-leftest[depth]+1)\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left, depth+1, idx*2)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth+1, idx*2+1)\n",
    "\n",
    "        dfs(root, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        mapper = dict()\n",
    "\n",
    "        def dfs(node, depth, idx):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            nonlocal res\n",
    "            if depth in mapper:\n",
    "                res = max(res, idx-mapper[depth]+1)\n",
    "            else:\n",
    "                mapper[depth] = idx\n",
    "            \n",
    "            dfs(node.left, depth+1, 2*idx)\n",
    "            dfs(node.right, depth+1, 2*idx+1)\n",
    "        \n",
    "        dfs(root, 0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "\n",
    "        leftest = {}\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node, depth, idx):\n",
    "            nonlocal res\n",
    "\n",
    "            if depth in leftest:\n",
    "                leftest[depth] = min(leftest[depth], idx)\n",
    "            else:\n",
    "                leftest[depth] = idx\n",
    "            \n",
    "            res = max(res, idx-leftest[depth]+1)\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left, depth+1, idx*2)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth+1, idx*2+1)\n",
    "\n",
    "        dfs(root, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        levels = {}\n",
    "\n",
    "        def dfs(node, level, idx):\n",
    "            if not node: return 0\n",
    "            if level not in levels:\n",
    "                levels[level] = idx\n",
    "            return max(idx - levels[level] + 1, dfs(node.left, level + 1, idx * 2), dfs(node.right, level + 1, idx * 2 + 1))\n",
    "        return dfs(root, 1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\tdef widthOfBinaryTree(self, root):\n",
    "\t\ta = {}\n",
    "\t\tdef dfs(node, i, level):\n",
    "\t\t\tif node:\n",
    "\t\t\t\tif level not in a: a[level] = [i, i]\n",
    "\t\t\t\telse: a[level][1] = i\n",
    "\t\t\t\tdfs(node.left, i * 2 + 1, level + 1)\n",
    "\t\t\t\tdfs(node.right, i * 2 + 2, level + 1)\n",
    "\t\tdfs(root, 0, 0)\n",
    "\t\treturn max([y - x + 1 for _, (x, y) in a.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        levelMin = {}\n",
    "        def dfs(node: Optional[TreeNode], depth: int, index: int) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if depth not in levelMin:\n",
    "                levelMin[depth] = index  # 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值\n",
    "            return max(index - levelMin[depth] + 1,\n",
    "                       dfs(node.left, depth + 1, index * 2),\n",
    "                       dfs(node.right, depth + 1, index * 2 + 1))\n",
    "        return dfs(root, 1, 1)\n",
    "\n",
    "# 链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/solutions/1776589/er-cha-shu-zui-da-kuan-du-by-leetcode-so-9zp3/\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
